import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 1006. 笨阶乘
 * https://leetcode-cn.com/problems/clumsy-factorial/
 */
public class Solutions_1006 {
    public static void main(String[] args) {
        int num1 = 4;  // output: 7
        int num2 = 10;  // output: 12

        List<Integer> inputs = new ArrayList<>();
        inputs.add(num1);
        inputs.add(num2);

        for (int input : inputs) {
            int result = clumsy(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：栈
     */
    public static int clumsy(int N) {
        int res = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.add(N);
        N --;
        int idx = 0;
        while (N > 0) {
            if (idx % 4 == 0) {
                // 与前一元素相乘
                stack.push(stack.pop() * N);
            } else if (idx % 4 == 1) {
                // 与前一元素相乘
                stack.push(stack.pop() / N);
            } else if (idx % 4 == 2) {
                // 加号
                stack.push(N);
            } else if (idx % 4 == 3) {
                // 减号
                stack.push(-N);
            }
            N --;
            idx ++;
        }
        // 取出 stack 元素
        while (!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }
}
